# 找出一个整数数组中子数组之和的最大值
# sample input: nums = [1, -2, 3, -8, 5, 1]
# samput output: ans = 6
# 思路: dp维护区间极大值，取极大值中最大的为答案

nums = [1, -2, 3, -8, 5, 1]
tot = 0
ans = 0

for num in nums:
    if tot > 0:
        tot += num
    else:
        tot = num
    
    ans = max(tot, ans)

print(ans)